/*
leetcode 767
*/
#include<bits/stdc++.h>
using namespace std;
class Solution {
private:
	bool static cmp(pair<int,int> &a,pair<int,int> &b){
		return a.second>b.second;
	}
public:
    string reorganizeString(string s) {
		unordered_map<char,int> mp;
		int maxcount=0;
		for(char &ch:s){
			mp[ch]++;
			maxcount=max(maxcount,mp[ch]);
		}
		if(maxcount*2>s.size()+1) return "";
		vector<pair<int,int>> vec(mp.begin(),mp.end());
		sort(vec.begin(),vec.end(),cmp);
        int n=s.size();
        //注意这里：在创建一个新的字符串时，要给它规定大小，这里表示和题目给的字符串s的大小相同
        string str(n, ' ');
        //这样也可以，表示这个字符串的大小为n,初始化的内容为空字符串' '
		string str(s);
		int index=0;
		for(auto &i:vec){
			while(i.second--){
				str[index]=i.first;
				index+=2;
				if(index>=s.size()) index=1;
			}
		}
		return str;
    }
};